package Dungeoneering.PathFinding.DataStructures;

import java.awt.Point;
import java.util.HashMap;

import Dungeoneering.Entities.Room;
import Dungeoneering.Entities.Room.Direction;
import Dungeoneering.PathFinding.Path;
import Dungeoneering.PathFinding.PathNode;

/**
 * We store our rooms in a 4-Tree so we can easely virtually travel through our dungeon so we can easely find paths
 * @author Nicolaas
 *
 */
public class QuaternaryTree {
	
	private TreeNode root;
	
	private TreeNode selectedNode;
	
	private HashMap<Point, TreeNode> map;
	
	public QuaternaryTree(Room root) {
		map = new HashMap<Point, TreeNode>();
		this.root = new TreeNode(root);
		this.selectedNode = this.root;
		map.put(root.getMapCoords(), this.root);
	}
	
	public Room getSelected() {
		return selectedNode.get();
	}
	
	public void select(Room r) {
		Point p = r.getMapCoords();
		if (map.get(p) == null)
			add(r);
		selectedNode = map.get(p);
	}
	
	public void add(Room room) {
		if (map.containsKey(room.getMapCoords()))
			return;
		TreeNode node = new TreeNode(room);
		Point p = room.getMapCoords();
		map.put(p, node);
		
		// north
		TreeNode north = map.get(new Point(p.x, p.y - 1));
		if (north != null && north.get().getDoor(Direction.SOUTH) != null) {
			// north room exists and has a south door, so we add the link
			north.setLink(node, Direction.SOUTH);
			node.setLink(north, Direction.NORTH);
		}
		
		// east
		TreeNode east = map.get(new Point(p.x + 1, p.y));
		if (east != null && east.get().getDoor(Direction.WEST) != null) {
			// north room exists, so we add the link
			east.setLink(node, Direction.WEST);
			node.setLink(east, Direction.EAST);
		}
		
		// south
		TreeNode south = map.get(new Point(p.x, p.y + 1));
		if (south != null && south.get().getDoor(Direction.NORTH) != null) {
			south.setLink(node, Direction.NORTH);
			node.setLink(south, Direction.SOUTH);
		}
		
		// west
		TreeNode west = map.get(new Point(p.x - 1, p.y));
		if (west != null && west.get().getDoor(Direction.EAST) != null) {
			west.setLink(node, Direction.EAST);
			node.setLink(west, Direction.WEST);
		}
		
		
	}
	
	public boolean findPath(Room start, Room end, Path path) {
		if (map.get(start.getMapCoords()) == null || map.get(end.getMapCoords()) == null)
			return false;
		return depthFirstSearch(map.get(start.getMapCoords()), map.get(end.getMapCoords()), path);
		
	}
	
	private boolean depthFirstSearch(TreeNode start, TreeNode end, Path path) {
		// make sure we arent stuck in a loop
		if (path.contains(start.get().getMapCoords()))
			return false;
		PathNode node = new PathNode(start.get().getMapCoords());
		path.push(node);
		
		if (start == end)
			return true;
		if (start.hasLink(Direction.NORTH)) {
			if (depthFirstSearch(start.get(Direction.NORTH), end, path)) {
				node.setDirectionToNextNode(Direction.NORTH);
				return true;
			}
		}
		if (start.hasLink(Direction.EAST)) {
			if (depthFirstSearch(start.get(Direction.EAST), end, path)) {
				node.setDirectionToNextNode(Direction.EAST);
				return true;
			}
		}
		if (start.hasLink(Direction.SOUTH)) {
			if (depthFirstSearch(start.get(Direction.SOUTH), end, path)) {
				node.setDirectionToNextNode(Direction.SOUTH);
				return true;
			}
		}
		if (start.hasLink(Direction.WEST)) {
			if (depthFirstSearch(start.get(Direction.WEST), end, path)) {
				node.setDirectionToNextNode(Direction.WEST);
				return true;
			}
		}
		path.pop();
		return false;
	}
	

}
